package main

import (
	"fmt"
	"sort"
)

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums)
	ans := [][]int{}
	for i := 0; i < len(nums)-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
		if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[len(nums)-3]+nums[len(nums)-2]+nums[len(nums)-1] < target {
			continue
		}
		for j := i + 1; j < len(nums)-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
			if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[len(nums)-2]+nums[len(nums)-1] < target {
				continue
			}
			left, right := j+1, len(nums)-1
			for left < right {
				sum := nums[i] + nums[j] + nums[left] + nums[right]
				//&& !arrayExists(ans, []int{nums[i], nums[j], nums[left], nums[right]})
				if sum == target {
					ans = append(ans, []int{nums[i], nums[j], nums[left], nums[right]})
					left++
					for left < right && nums[left] == nums[left-1] {
						left++
					}
					right--
					for left < right && nums[right] == nums[right+1] {
						right--
					}
				} else if sum < target {
					left++
				} else {
					right--
				}

			}
		}
	}
	return ans
}

func main() {
	fmt.Println("[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]\n", fourSum([]int{1, 0, -1, 0, -2, 2}, 0))
	fmt.Println("[[2,2,2,2]]\n", fourSum([]int{2, 2, 2, 2, 2}, 8))
}
